package medium

/*
时间复杂度:O(N)
空间复杂度:O(1)

难点：找到符合条件的窗口很容易，但是如何计算窗口内的子数组数量?
解决： 以[10 5 1 6]，k=100为例，这里求的是乘积<k的所有子数组数量,第一个符合条件的窗口是[10],然后是[10,5],每次right右移时，增加的是[5], [10, 5]
第三个窗口是[10 5 1]增加的是[1] [5 1] [10 5 1]; 也就是每次增加的是以nums[right]为右边界的子数组;
之后[10 5 1 6]不符合，left++, [5 1 6]符合,此时增加的是[6] [1 6] [5 1 6]
*/

func numSubarrayProductLessThanK(nums []int, k int) int {
	left, right := 0, 0
	ans := 0
	windowVal := 1

	for right < len(nums) {
		windowVal *= nums[right]
		// 由于是乘积<k才符合条件，所以当windowVal >= k时，乘积是大于等于k的，需要将left右移
		for left<= right && windowVal >= k {
			windowVal /= nums[left]
			left++
		}
		ans += right - left + 1
		right++
	}
	return ans
}
